"""
------------------------------------------
@File       : bin_search.py
@CreatedOn  : 2022/4/20 0:38
------------------------------------------
二分查找，防内存溢出版
"""


def searching_show(lis, middle):
    arrow_left_len = 1 + 1 + middle * 3
    arrow_content = '↑'.rjust(arrow_left_len, ' ')
    print(f"middle: {middle}\n{lis}\n{arrow_content}\n")


def bin_search(lis, target):
    """
        计算中的 end = middle - 1 和 start = middle + 1可以理解为将比较过的middle元素在新的搜索区间去掉，不重复比较。

    :param lis:
    :param target:
    :return:
    """
    start = 0
    end = len(lis) - 1

    if end < 1:
        return -1

    while start <= end:
        middle = start + ((end - start) >> 1)
        searching_show(lis, middle)

        if lis[middle] == target:
            return middle

        elif target < lis[middle]:
            end = middle - 1

        elif target > lis[middle]:
            start = middle + 1

    return -1


if __name__ == '__main__':
    lis1 = [1, 2, 3, 4, 5, 6, 7]
    search_value = 7
    result = bin_search(lis1, search_value)
    print(f"result: {result}")
